package 校招笔试.美团笔试.美23812;

import org.junit.Test;

import java.util.*;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/8/14 20:26
 */
public class one {

    //题目 链接 https://mp.weixin.qq.com/s/NVSAjmmL48_PtLIOKXVQqg

//    小美拿到了一个排列。她想知道在这个排列中，x和y是否是相邻的。你能帮帮她吗？
//
//    排列是指一个长度为n的数组，其中 1 到n 每个元素恰好出现一次。


    static Scanner sc = new Scanner(System.in);


    public static void main1(String[] args) {
        int n = sc.nextInt();
        int nums[] = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        int a = sc.nextInt(), b = sc.nextInt();

        for (int i = 0; i < n; i++) {
            if (nums[i] == a) {
                if ((i < n - 1 && nums[i + 1] == b) || (i > 0 && nums[i - 1] == b)) {
                    System.out.println("Yes");
                    return;
                }
            }

        }
        System.out.println("No");
    }


    // 二
    /*
      注意数据量
      可能 会溢出， 不要在 这个 地方 耽搁 太多的时间

     学习 一下 环形 数组的遍历 方法，  正序， 和 逆序
     */
    public static void main2(String[] args) {
        int n = sc.nextInt();
        int nums[] = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        int x = sc.nextInt() - 1, y = sc.nextInt() - 1;
        long sum1 =0 ,sum2 = 0;
        // 顺时针
        int cur = x;
        while(cur != y){
            sum1 += nums[cur];

            cur = (cur + 1) % n;
            if(cur == 0){ // 说明 走到 头了 ，需要从 0 开始走
                cur = 0;
            }
        }

        // 逆时针 , 这个 逆时针 遍历 是真的 有意思！
        cur = x;
        while(cur != y){
            sum2 += cur == 0 ? nums[n - 1] : nums[cur - 1];

            cur--;
            if(cur == -1){ // 需要 退到 n - 1
                cur = n - 1;
            }
        }

        System.out.println(Math.min(sum1,sum2));

    }


    // 三

    public static void main3(String[] args) {
        int n = sc.nextInt(), m = sc.nextInt();
        int matrix[][] = new int[n][m];
//        int preSum[][] = new int[n + 1][m];
//        int preRow[] = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = sc.nextInt();
                sum += matrix[i][j];
            }
        }
        int ans = Integer.MAX_VALUE;
        int rowSum = 0;
        for (int i = 0; i < n - 1; i++) {
            rowSum += Arrays.stream(matrix[i]).sum();
            ans = Math.min(Math.abs(sum - rowSum - rowSum), ans);
        }
        int colSum = 0;
        for (int j = 0; j < m - 1; j++) {
            for (int i = 0; i < n; i++) {
                colSum += matrix[i][j];
            }
            ans = Math.min(Math.abs(sum - colSum - colSum), ans);
        }
        System.out.println(ans);
    }


    /*
      树 染色,
      这个 题 跟 打家劫舍 III  有点 类似
      但是比那个 难多了!
     */
    public static void main$(String[] args) {

        int n = sc.nextInt();
        HashMap<Integer, Node> tree = new HashMap<>();

        for (int i = 1; i <= n; i++) {
            int val = sc.nextInt();
            tree.put(i, new Node(val));
        }
        for (int i = 1; i < n; i++) {
            int node = sc.nextInt();
            int next = sc.nextInt();
            tree.get(node).nexts.add(next);
        }
        int[] ints = solve1(tree, 1);
        System.out.println(Math.max(ints[0], ints[1]));
    }

    static class Node {
        int val;
        List<Integer> nexts;

        public Node(int val) {
            this.val = val;
            nexts = new ArrayList<>();
        }

    }

    // 树形dp 也不太好写
    // 考虑的太片面, 再选择 头节点的时候, 考虑的太片面,理解问题
//    https://codefun2000.com/p/P1445/solution    // 通过 这个 java 的题解 直接明白了
    //  res[1] = Math.max(res[1], res[0] - mx + 2 + t[0]);  // 而且还学到了一种新的 建图(树)的方式,   v ,p (无向图)法
    private static int[] solve1(HashMap<Integer, Node> tree, int node) {
        if (tree.get(node).nexts.isEmpty()) {
            return new int[]{0, 0};
        }
        int ans1 = 0, ans2 = 0; // ans1 表示 不偷 头节点, ans2  表示偷 头节点
        for (Integer next : tree.get(node).nexts) {
            // 不偷 头节点
            int[] ints = solve1(tree, next);
            ans1 += Math.max(ints[0], ints[1]);

            // stole  node
            long temp = tree.get(node).val;
            int v = 0;
            if (judge(temp * tree.get(next).val)) {
                for (Integer nnext : tree.get(next).nexts) {
//                  虾米这个好像 不需要了, 因为上面 的 slove1 已经计算过了好像!
                    int[] ints1 = solve1(tree, nnext);
//                    v += Math.max(ints1[0],ints1[1]);
                    v += ints1[0];
                    ans2 = Math.max(ans2,ints[0]);
                }
//                v = v + 2;
//                ans2 = Math.max(ans2, v);
            }
            // v 是当前这棵树子树, 但是还要加上 其他的 子树的, 就这点出现了问题
        }
//        return Math.max(ans1,ans2);
        return new int[]{ans1, ans2};

    }


    // 不完全正确
    private static int solve(HashMap<Integer, Node> tree, int node) {
        if (tree.get(node).nexts.isEmpty()) {
            return 0;
        }
        int ans1 = 0, ans2 = 0;
        for (Integer next : tree.get(node).nexts) {
            // 不选
            ans1 += solve(tree, next);
            // 选
            int mul = tree.get(node).val;
            int temp = 0;
            if (judge(mul * tree.get(next).val)) { // 判断相邻节点是否  完全平方
                // yes
                for (Integer nnext : tree.get(next).nexts) { // 跳到 nnext 节点
                    temp += solve(tree, nnext);
                }
//                ans2 += temp + 2;
                temp = temp + 2;
            }
            ans2 = Math.max(ans2, temp);

        }
        return Math.max(ans1, ans2);

    }

    // 判断是不是完全平方数
    private static boolean judge(long x) {
        int temp = (int) Math.sqrt(x);
        return temp * temp == x;
    }


    // 小美的 排列构造 , 这是真他妈垃圾

    public static void main(String args[]) {
        int n = sc.nextInt();
        int nums[] = new int[n + 1];
        int l = 1, r = n;
        int li = 1, ri = n;
        boolean flag = false;
        while (l < r) {
            if (!flag) {
                nums[ri--] = r--;
                if (r > l) {
                    nums[li++] = r--;
                }
                flag = true;
            } else {
                nums[ri--] = l++;
                nums[li++] = l++;
                flag = false;
            }
        }
        nums[ri] = nums[ri] == 0 ? r : nums[ri];
        for (int i = 1; i <= n; i++) {
            System.out.printf(nums[i] + " ");
        }

    }

    public static void f(int n) {
        int l = 1,r = n;
        while(l < r){
            System.out.printf(l + " ");
            System.out.printf(r + " ");
            r--;
            l++;
        }
        if(l == r){
            System.out.println(l);
        }
    }


    @Test
    public void test() {
        f(5);
        f(6);
        f(3);
    }

}
